package com.algorithm;

import java.util.Arrays;

/**
 * 插入排序-犹如扑克牌排序
 * 犹如打扑克牌，把下一个数据插入之前排好序的数组的正确位置，如果只是一个，无需排序
 * 后续的依照此规则继续进行
 */
public class InsertionSort {

    public static int[] sort(int[] arrSource){
        // 对 arr 进行拷贝，不改变参数内容
          int[]  arr = Arrays.copyOf(arrSource,arrSource.length);
        // 从下标为1的元素开始选择合适的位置插入，因为下标为0的只有一个元素，默认是有序的
          for(int i=1;i<arrSource.length;i++){
              // 记录要插入的数据
              int temp = arr[i];
              int j = i;
              // 从已经排序的序列最右边的开始比较，找到比其小的数
              while(j>0&&temp<arr[j-1]){//找到一个，交换一个(移位)
                  arr[j] = arr[j-1];//数据后移，神操作！
                  j--;
              }
              // 存在比其小的数，插入
              if(j!=i){
                  arr[j] = temp;
              }
              System.out.println("排序中:"+Arrays.toString(arr));
          }

          return arr;
    }

    public static int[] sort2(int[] arrSource) {
        int[] arr = Arrays.copyOf(arrSource,arrSource.length);
        for(int i=1;i<arr.length;i++){
            int temp = arr[i];
            int j = i;
            while(j>0 && temp<arr[j-1]){
                arr[j] = arr[j-1];
                j--;
            }
            if(j!=i){
                arr[j] = temp;
            }
            System.out.println("sort2排序中:"+Arrays.toString(arr));
        }
        return arr;
    }

    public  static int[] sort3(int[] arrSource){
        int[] arr = Arrays.copyOf(arrSource,arrSource.length);
        for(int i=0;i<arr.length-1;i++){
            int temp = arr[i+1];
            int j = i+1;
            while(j>0&&arr[j-1]>temp){
                arr[j]=arr[j-1];
                j--;
            }
            if(j!=(i+1))
                arr[j] = temp;
            System.out.println("sort3排序中:"+Arrays.toString(arr));
        }

        return arr;
    }

    public static int[] sort4(int[] arrSource){
        int[] arr = Arrays.copyOf(arrSource,arrSource.length);
        for(int i=1;i<arr.length;i++){
            int j = i;
            int temp = arr[i];
            while(j>0&&arr[j-1]>temp){
                arr[j] = arr[j-1];
                j--;
            }
            if(j!=i){
                arr[j] = temp;
            }
            System.out.println("sort4排序中:"+Arrays.toString(arr));
        }
        return arr;
    }
    public static void main(String[] args) {

        int[] sort = new int[]{8, 9, 10, 3, 2, 4, 5, 6, 7, 1};
        System.out.println("排序前:" + Arrays.toString(sort));
        System.out.println("排序后:" + Arrays.toString(sort4(sort)));

    }


}
